|
計算複雑性理論におけるRP(randomized polynomial time)とは、以下の3つの属性を持つ確率的チューリング機械で解ける問題の複雑性クラスである。 * 入力長に対して常に多項式時間かかる。 * 正解が NO である場合、常に NO を返す。 * 正解が YES である場合、確率 ½ 以上で YES を返す（そうでない場合、NO を返す）。 換言すれば、そのアルゴリズムは、実行中に完全に無作為なコインを投げているようなものである。このアルゴリズムが YES を返すのは、実際の答えが YES であるときだけである。したがって、アルゴリズムが停止して YES を生成した場合、正解は必ず YES である。しかし、NO を返して停止する場合、実際の答えが何であるかはわからない。つまり、NO を返したとき、それは間違っている可能性がある。 この複雑性クラスを R と呼ぶこともあるが、一般に R と言えば帰納言語のクラスの名称として使われている。 正解が YES であるとき、このアルゴリズムを ''n'' 回試行し、各試行には確率論的独立性があるとき、YES が少なくとも 1回返される確率は 1 - ½''n'' 以上である。従って、100回試行すれば回答が間違っている確率は、宇宙線がコンピュータのメモリの内容を破壊して計算結果を間違う可能性よりも低くなる。従って、乱数発生源があれば、RP に属するアルゴリズムの多くは極めて実用的となる。 ½ という割合は実際には任意の割合でよい。½ が 0 より大きく 1 より小さい任意の割合でありさえすれば、RP に属する問題の性質は変わらない。この定数はアルゴリズムの入力の内容や長さとは無関係である。 == 関連する複雑性クラス == RP の定義によれば、YES という解は常に正しく、NO という解はおおむね正しい。Co-RP クラスも同様に定義でき、NO という解が常に正しく、YES という解がおおむね正しい。換言すれば、Co-RP に相当するチューリング機械は YES となるべき入力は常に受理するが、NO となるべき入力は受理するか不受理かのどちらかとなる。BPP クラスは正解が YES であっても NO であっても間違う可能性のあるアルゴリズムに相当する。RP と Co-RP の積集合に相当するクラスを ZPP と呼ぶ。RP を R と呼ぶように、Co-RP を Co-R と呼ぶことがある。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「RP (計算複雑性理論)」の詳細全文を読む スポンサード リンク
|